# PrimeSieve.rb
# July 21, 2007
#

# 9. Juli 2007
#


def prime_factor(n)
  a=prime_calc(n)
  i=0
  r=[]
  s=''
  while i<a.length
    r[a[i]]=division_count(n, a[i])
    i+=1
  end
  r.each_with_index do |x, index|
    if x!=nil && x>=1
      s<<index.to_s + "^" + x.to_s + " "
    end 
  end
  s
end

  
def division_count(n, t)
  i=0
  r=n
  while r%t==0
    r=r/t
    i+=1
  end
  i
end


def prime_calc(n)
  i=2
  k=0
  a=[]
      
  while k<=n-2
    a[k]=k+2
    k+=1
  end
      
  while i<=n
    j=2
    while i*j<=n
      a[i*j-2]=nil
      j+=1
    end
    i+=1
  end
  a.compact
end


a=gets.to_i
puts a.to_s + ": " + prime_factor(a)
